The security of cryptographic constructions relies on some secret information to which should be accessible by honest parties and legitimate users, but which should not be accessible by malicious parties or non-legitimate users. Accordingly, the security properties of any computing system that makes use of cryptographic constructions hold under the assumption that certain secret information (typically, comprising one or more secret keys) is and remains unknown by any attacker against the system.
In general, the security of any such system is immediately compromised once this secret information, referred to as secret state, is exposed (in public or to an attacker against the system). For instance, the secret state can simply comprise one secret key and if this key leaks to an attacker, then both the underlying cryptographic construction and the higher-application system become vulnerable to trivial attacks. This fatal exposure of the secret information is a serious real-life problem: secret keys may be lost accidentally or erroneously due to human mistakes or due to incorrect key-management practices, or they may be stolen as a result of sophisticated attacks against the system. Therefore, it is important to apply additional security mechanisms that protect against such secret-state exposures.
Forward security refers to a cryptographic property according to which an exposed secret key can affect the security of the underlying system only in the future but not in the past. Forward security is implemented in practice through systematic pseudorandom key updates, so that the usage of older keys in the past remains secure indefinitely in the future, despite any possible compromises of newer keys that may occur in the future. However, this key-update procedure introduces additional computational and storage overheads in the system, especially for applications where keys must be updated asynchronously or on demand, i.e., a new key that is “distant” from the current key must be produced, thus the key-update procedure must operate in a “jump-ahead” fashion.
A need exists for forward-secure pseudorandom generators (FS-PRNGs) that are forward secure as well as efficient with respect to their key-update processes. In other words, a need remains for FS-PRNG schemes that incur low catch-up costs while keeping the required storage small possible. A further need remains for FS-PRNG schemes that are as general as possible, thus covering a wide range of possible applications, and that can support additional security practices.